// 239.滑动窗口最大值

package LeetcodeHot100;

import java.util.Comparator;
import java.util.PriorityQueue;

public class Solution239 {
    public int[] maxSlidingWindow(int[] nums, int k) {
        // 初始化优先队列，并指定比较方式
        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>(new Comparator<int[]>() {
            public int compare(int[] pair1, int[] pair2) {
                return pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair1[1];
            }
        });
        // 将前 k 个元素入队
        for (int i = 0; i < k; i++) {
            priorityQueue.offer(new int[] { nums[i], i });
        }

        int[] result = new int[nums.length - k + 1]; // 存储最终的结果
        result[0] = priorityQueue.peek()[0];

        for (int i = k; i < nums.length; i++) {
            priorityQueue.offer(new int[] { nums[i], i });
            // 这里不能是 == ，并且要使用 while，因为可能最大的都不在子区间内
            while (priorityQueue.peek()[1] <= i - k)
                priorityQueue.poll();
            result[i - k + 1] = priorityQueue.peek()[0];
        }
        return result;
    }
}
